class Solution(object):
    def numSubmat(self, mat):
        m = len(mat)
        n = len(mat[0])
        pref = [[0 for _ in range(n)] for _ in range(m)]
        for j in range(n):
            for i in range(m):
                if i == 0:
                    pref[i][j] = mat[i][j]
                else:
                    if mat[i][j]:
                        pref[i][j] = pref[i - 1][j] + mat[i][j]
                    else:
                        pref[i][j] = 0
        ans = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    ans += pref[i][j]
                    now_min = pref[i][j]
                    for k in range(j - 1, -1, -1):
                        if mat[i][k]:
                            now_min = min(now_min, pref[i][k])
                            ans += now_min
                        else:
                            break
        return ans


data = Solution()
mat = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
print(data.numSubmat(mat))
